(Problem) 007 10001st prime

Project Euler

• 공식 홈페이지 - projecteuler.net
• 한글 번역 - projecteuler @kr
• (HackerRank) ProjectEuler+ - hackerrank.com

Problem

Problem list

• No 7 : 10001st prime
  • HackerRank : Project Euler #7: 10001st prime

10001st prime

problem <번역>

solution

Simple Code

특정한 숫자가 소수인지 판별하는 것이 아니라 계속해서 소수를 찾아가면서 몇 번째인지 찾는게 어려웠다ㅠ
굉장히 Brute Force 적인 방식으로 풀었다(그래서 시간이 오래 걸린다)

007_10001st_prime.py

def nth_prime(idx):
  primes = [2, 3]
  pivot = 6

  while len(primes) < idx:
      is_prime = True
      for prime in primes:
          if int(pivot-1) % int(prime) == 0:    # 5, 11, 17, ...
              is_prime = False
              break

      if is_prime:
          primes.append(pivot-1)

      is_prime = True
      for prime in primes:
          if int(pivot+1) % int(prime) == 0:    # 7, 13, 19, ...
              is_prime = False
              break

      if is_prime:
          primes.append(pivot+1)

      pivot += 6

  return primes[-1]


print(nth_prime(10001))  

sympy 모듈을 사용하면 매우 간단하게 구현 가능하다

007_with_sympy.py

from sympy import prime

print(prime(10001)) 

---

HackerRank

해커랭크 풀이

007_for_HacerRank.py

def sieve_of_eratosthenes(n):
    sieve = {}
    prime = 2
    cnt = 0

    while cnt < n:
        if prime not in sieve:
            yield prime
            cnt += 1
            sieve[prime * prime] = [prime]
        else:
            for p in sieve[prime]:
                sieve.setdefault(p + prime, []).append(p)
            del sieve[prime]
        prime += 1


if __name__ == '__main__':
    lin = []
    for _ in range(int(input())):
        lin.append(int(input()))

    primes = list(sieve_of_eratosthenes(max(lin)))
    for i in lin:
        print(primes[i - 1])

생각보다 너무 어려웠다ㅠ